不妨设 , 且$ n < m $。

回忆一下卡塔兰数的推导过程 , 我们用类似的方法解决此题。
首先,我们可将题意转化成从到,不穿过的一条路径。
将向上平移一个单位得(黄色的函数),原题等价于求一条路径且不经过的路径。
从反面思考,我们只需找到经过的路径即可。
我们不妨将关于作对称得到,发现对于每一条的路径,都会穿过 , 且一定有一条的路径与之对应。(蓝色虚线与红色实线)
那么经过的路径的数量为
又因为从起点到终点的路径一共有
所以答案为
还有两种特殊情况:
1. , 此时直接输出。
2. , 此时直接输出。
这道题的都很大,建议用自然对数的形式存阶乘。
#include <cstdio>
#include <cmath>
const int MAXN = 300000;
int n , m , k;
double Ans , Fac[ MAXN + 5 ];
void Init( ) {
Fac[ 0 ] = 0;
for( int i = 1 ; i <= MAXN ; i ++ )
Fac[ i ] = Fac[ i - 1 ] + log( i * 1.0 );
}
double C( int n , int m ) {
return Fac[ n ] - Fac[ m ] - Fac[ n - m ];
}
int main( ) {
Init( );
scanf("%d %d %d",&n,&m,&k);
if( k >= m )
Ans = 1;
else if( n + k < m )
Ans = 0;
else
Ans = 1 - exp( C( n + m , n + k + 1 ) - C( n + m , n ) );
printf("%.6lf",Ans);
return 0;
}